`
https://leetcode.cn/problems/shortest-path-in-binary-matrix/
`

/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestPathBinaryMatrix = function (grid) {
  const n = grid.length
  if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) {
    return -1
  }

  // 向八个方向扩散
  const dirs = [
    [0, 1], [0, -1], [1, 0], [-1, 0],
    [1, 1], [1, -1], [-1, 1], [-1, -1]
  ]

  const q = [[0, 0]]
  const visited = Array.from({ length: n }, () => new Array(n).fill(false))
  visited[0][0] = true
  let step = 0

  // BFS
  while (q.length) {
    const sz = q.length
    step++
    for (let _ = 0; _ < sz; _++) {
      const [x, y] = q.shift()
      if (x === n - 1 && y === n - 1) {
        return step
      }
      // 向八个方向扩散
      for (const dir of dirs) {
        const nextX = x + dir[0]
        const nextY = y + dir[1]
        // 确保相邻的这个坐标没有越界且值为 0 且之前没有走过
        if (
          nextX >= 0 && nextX < n && nextY >= 0 && nextY < n &&
          grid[nextX][nextY] === 0 && !visited[nextX][nextY]
        ) {
          visited[nextX][nextY] = true
          q.push([nextX, nextY])
        }
      }
    }
  }

  return -1
};